#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using li=__int128;
using pi=pair<int,int>;
#define fi first
#define se second
const int N=4e5+5;
int n;
mt19937 rd(5384);
struct fhq{
    int rt,tot,ch[N][2],sz[N],R[N];
    ll val[N],s[N];li f[N],g[N];
    inline int Sz(){return sz[rt];}
    inline void upd(int p) {
        s[p]=s[ch[p][0]]+s[ch[p][1]]+val[p],sz[p]=sz[ch[p][0]]+sz[ch[p][1]]+1;
        f[p]=f[ch[p][0]]+(li)(s[ch[p][0]]+val[p])*(sz[ch[p][1]]+1)+f[ch[p][1]];
        g[p]=g[ch[p][1]]+(li)(s[ch[p][1]]+val[p])*(sz[ch[p][0]]+1)+g[ch[p][0]];
    }
    pi split(int p,ll v) {
        if(!p)return {};pi w;
        if(val[p]<=v)return w=split(ch[p][1],v),ch[p][1]=w.fi,upd(p),pi{p,w.se};
        return w=split(ch[p][0],v),ch[p][0]=w.se,upd(p),pi{w.fi,p};
    }
    pi split1(int p,int k) {
        if(!p)return {};pi w;
        if(sz[ch[p][0]]>=k)return w=split1(ch[p][0],k),ch[p][0]=w.se,upd(p),pi{w.fi,p};
        return w=split1(ch[p][1],k-sz[ch[p][0]]-1),ch[p][1]=w.fi,upd(p),pi{p,w.se};
    }
    int merge(int p,int q) {
        if(!p||!q)return p+q;
        if(R[p]<R[q])return ch[p][1]=merge(ch[p][1],q),upd(p),p;
        return ch[q][0]=merge(p,ch[q][0]),upd(q),q;
    }
    void ins(ll x) {
        pi w1=split(rt,x),w2=split(w1.fi,x-1);
        if(!w2.se) {
            R[++tot]=rd(),s[tot]=val[tot]=x,sz[tot]=1;
            rt=merge(w2.fi,merge(tot,w1.se));
        }else rt=merge(w2.fi,w1.se);
    }
    ll pre(int k) {
        pi w=split1(rt,k);ll S=s[w.fi];
        return rt=merge(w.fi,w.se),S;
    }
    ll suf(int k) {
        pi w=split1(rt,sz[rt]-k);ll S=s[w.se];
        return rt=merge(w.fi,w.se),S;
    }
    li F1(int l,int r) {
        pi w1=split1(rt,l-1),w2=split1(w1.se,r-l+1);
        li ans=f[w2.fi]+(li)s[w1.fi]*sz[w2.fi];
        return rt=merge(w1.fi,merge(w2.fi,w2.se)),ans;
    }
    li F2(int l,int r) {
        pi w1=split1(rt,sz[rt]-r),w2=split1(w1.se,r-l+1);
        li ans=g[w2.fi]+(li)s[w2.se]*sz[w2.fi];
        return rt=merge(w1.fi,merge(w2.fi,w2.se)),ans;
    }
    ll F(int l,int r){return l>r?0:F2(l,r)-F1(l,r);}
}T;
int main() {
    freopen("kte.in","r",stdin);
    freopen("kte.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    while(n--) {
        ll x,ans=0;cin>>x,T.ins(x);
        int m=T.Sz();
        if(m<=5) {
            ll mxr=0,mxl=0;
            for(int i=1;i<=m;i++) {
                ll L=T.pre(i),R=T.suf(i);
                if(L>mxr)ans+=mxr-mxl,mxl=L;
                mxr=R;
            }cout<<ans+mxr-mxl<<'\n';
            continue;
        }
        int k=m/2+1;
        if(T.suf(k-1)-T.pre(k)<0) {
            cout<<T.F(1,m)<<'\n';
        }else {
            int l=1,r=k,mid,lc=k,rc=k;
            if(T.suf(1)-T.pre(2)>=0)lc=2;
            else while(l<=r)mid=l+r>>1,T.suf(mid-1)-T.pre(mid)>=0?r=mid-1,lc=mid:l=mid+1;
            l=k,r=m-1;
            if(T.suf(m-2)-T.pre(m-1)>=0)rc=m-1;
            else while(l<=r)mid=l+r>>1,T.suf(mid-1)-T.pre(mid)>=0?l=mid+1,rc=mid:r=mid-1;
            cout<<T.F(1,lc-2)+T.F(rc+1,m)+T.suf(rc)-T.pre(lc-1)<<'\n';
        }
    }
    return 0;
}